1. Field
The present disclosure is directed generally to communications protocols, and more particularly to methods of carrying out commercial transactions over a computer network.
2. Description
There is a trade-off between anonymity and reliability in transactions in all current electronic commerce systems. The relationship between anonymity and atomicity in electronic transactions is an open question. Some systems make reliability paramount and limit anonymity. Some systems attempt to provide both by providing conditional anonymity. Some systems provide anonymity at the price of reliability.
U.S. patent application Ser. No. 519,074, filed Aug. 24, 1995 and entitled Method and Apparatus for Purchasing and Delivering Digital Goods Over a Network, which application is assigned to the same assignee as the present invention, discloses a method for conducting an atomic transaction in which delivery of digital goods is carried out in a certifiable manner. In that protocol, provision is made for allowing transactions to take place under pseudonyms. However, the protocol is designed to provide the merchant with a customer identity, albeit a pseudonym. Thus, the need exists for an atomic transaction protocol that is anonymous.
There has been other work on Electronic commerce systems that:
provide methods for anonymous payment (type 1) or PA1 provide highly atomic protocols so that receiving a merchandise item is strongly associated with paying for the same merchandise (type 2). PA1 Money atomic transactions feature atomic transfer of electronic money--the transfer either completes entirely or not at all. In money atomic protocols, money is not created or destroyed by purchase transactions. PA1 Goods atomic transactions are money atomic and also ensure that the customer will receive merchandise if and only if the merchant is paid. Goods atomic transactions provide an atomic swap of the digital merchandise and funds--similar to the effect of "cash on delivery" parcels. PA1 Certified delivery protocols are goods atomic and also allow both the customer and merchant to prove exactly what was delivered. If there is a dispute, this evidence can be shown to a judge to prove exactly what merchandise were delivered. Using this classification, we can see that the simplified digital cash protocol described above is not money atomic. PA1 h(x) the hash of x PA1 E.sub.k (x) x, encrypted with symmetric key k PA1 P.sub.i (x) x, encrypted with the public key of i's private key set PA1 S.sub.i (x) x, encrypted with the secret key of i's private key set
Type 1 methods (anonymous payment) have revolved around protecting customer privacy through the use of token-based electronic payment protocols (so-called "digital cash" protocols.) These tokens are meant to act as a type of currency: they can be used to purchase merchandise, but like coins, they do not reveal the identity of the holder. These systems offer privacy in making a purchase. They provide customers with the ability to make anonymous purchases, purchases which cannot be tracked by a bank to identify the purchaser.
A stronger form of anonymity can be considered--anonymity in which the identity of the purchaser is hidden from both the bank and the merchant selling the merchandise. This raises the question of how the merchant will transmit the merchandise to the consumer without knowing the consumer's identity. A standard way of accomplishing this is through the use of intermediaries known as anonymizers or anonymous forwarders. If we have non-trackable tokens, then it is straightforward to use anonymizers to realize purchases that are anonymous to merchants, banks, and third parties.
The present prior art systems, however, are not fault tolerant. That is, ambiguous states arise when things go wrong. For example, if the network or merchant server goes down during a purchase, there is no mechanism to complain about non-delivered goods. If the purchases are anonymous, there is no way to prove that the customer really did pay and did not receive the merchandise. There is no trail to enable automated judges to adjudicate these complaints. Existing protocols are not sufficiently robust to enable judges or merchants to determine whether the customer was really denied the merchandise or whether the customer is just trying to illegitimately acquire merchandise for free. There is no mechanism in place to enable a customer to obtain satisfaction when the purchase is anonymous. These questions are especially important because the Internet today is an unreliable network--anyone who has spent some time browsing the World Wide Web knows that communications often fail. Unscrupulous customers and merchants will certainly attempt to take every advantage of system failures.
To illustrate the problem, consider the following simplified digital cash protocol: customers pay for digital merchandise with tokens. These tokens are anonymous, but designed so that if the customer ever uses the same token twice, the customer's identity is revealed. Suppose a customer pays for merchandise, but before she can receive acknowledgment that the merchant received payment, the network fails. Because the customer doesn't know whether the merchant received the payment or not, she has two basic strategies.
The first strategy is to spend the token again, by returning her token to the bank or spending it with a second merchant. But then, if the first merchant really did receive the token, she may be creating a race condition (i.e., a situation where, depending on timing, an inconsistent state may be created.) Whoever gets the token to the bank first will get the money. Worse, when both tokens do reach the bank, the customer will be accused of double-spending. One can imagine variations on the digital cash protocol where a customer might file a special type of complaint with a bank, but the design of this variation is non-trivial. Most types of variations will either reveal the customer's identity, allow a new type of fraud, be subject to ambiguous results if a message is not delivered, or have other undesirable effects. This topic is considered at length in: L. Jean Camr, Marvin Sirbu, and J. D. Tygar, Token and notational money in electronic commerce, In Proceedings of the First USENIX Workshop in Electronic Commerce, pages 1-12, July 1995; J. D. Tygar, Atomicity in electronic commerce, In Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, pages 8-26, May 1996 (based on a presentation given in August 1995.); and Bennet S. Yee, Using Secure Coprocessors, PhD thesis, Carnegie Mellon University, 1994.
The second strategy is to wait and not spend the money. But in that case, the customer has locked up her funds. If the merchant did not receive her payment, then the customer may be waiting for a very long time.
Methods of type 2 have addressed the question of reliability through the use of ACID (atomic, consistent, isolated, durable) transactions. See, for example, J. Gray and A. Reuter, Transaction Processing, Morgan-Kaufmann, 1993. These protocols have achieved fault-tolerance, that is, the ability to handle arbitrary communication failures and component failures of any party. In any case, the distributed system should always be in a consistent state: parties should agree on whether a transaction succeeded or not; when repairs are made, the distributed system should be able to continue processing without interruption.
In the distributed systems community, ACID transactions have been widely adopted as a standard mechanism for realizing fault-tolerant distributed transactions. Payment transactions should be failure-atomic, so that failures in parts of the system will not leave the entire system in some ambiguous, intermediate state.
The literature has suggested that these transactions be interpreted in the context of electronic commerce by using the classifications set forth below. Suppose we have a model where customers are purchasing digital merchandise and services that will be delivered over a network (e.g. a World Wide Web page). For tangible physical merchandise, alternative definitions are required to properly satisfy the atomicity property (motivating a multi-billion dollar industry in tracked, receipted courier delivery of messages and packages). The literature (See, for example, Tygar, Supra.) gives three classes of atomicity for digital merchandise.
Additional problems are raised in an anonymous atomic transactions. Indeed, the literature has speculated that anonymous atomic transactions might not even be possible. A traditional attempt to solve this question might be to use standard ACID techniques to make a digital cash transaction atomic. The most common method for ACID transactions is two-phase commitment. In short, in two-phase commitment, one party assumes the role of transaction coordinator. That party knows and records the identities of all other parties in a non-volatile archive. Each of the parties records its state before the transaction begins. As the transaction moves forward, various parties complete their required computation. Before changing the permanent store of those values, the parties send a message to the coordinator indicating that they are ready to commit. Alternatively, they may abort the transaction by sending a negative message to the coordinator. After receiving ready messages from all parties, the coordinator issues a commit message to all parties, causing the transaction to become permanent. Alternatively, if the coordinator receives an abort request or if the coordinator cannot establish contact with one of the parties, the coordinator can abort the transaction by sending an abort message; in that case, all parties reverse the computation that they conducted towards the transaction.
The two-phase commit protocol requires that at least one party participating in the protocol (the transaction coordinator) knows the identity of all the parties involved. Additionally, two-phase commit assumes; a fail-stop fault model, where the parties to the protocol can fail by stopping due to a crash or system failure, but not by lying or otherwise trying to cheat. In electronic commerce protocols, of course, we must be able to tolerate arbitrary faults (Byzantine faults). One way to do this is to provide sufficient auditing information to detect these faults and later assign responsibility. This makes the standard two-phase commit protocol inappropriate for use in anonymous electronic commerce systems.
An alternative approach to this problem was attempted by Jakobsson, Ripping coins for a fair exchange, In Louis C. Guillou and Jean-Jacques Quisquater, editors, Advances in Cryptology: Eurocrypt '95 Proceedings, Springer-Verlag 1995, where the payment protocol is divided into two halves. Here, the digital cash is "rip-spent": after the first half of the spending protocol, the customer has committed to buying from the merchant but has not yet spent the money--some partial information is transferred, so that if the customer attempts to abort the transaction, the digital cash is either lost (becomes unusable), or the identity of the customer is revealed. This approach is not satisfactory: each of the half protocols themselves may be interrupted, leaving the digital cash again in an ambiguous state. Thus, the need exists for a fault tolerant, atomic, transaction protocol that can maintain the anonymity of the customer.